package nachos.threads;

import nachos.machine.*;
import nachos.threads.PriorityScheduler.ThreadState;
import nachos.threads.PriorityScheduler.PriorityQueue.priorityComparator;
import java.util.*;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends PriorityScheduler {
    /**
     * Allocate a new lottery scheduler.
     */
    public LotteryScheduler() {
    }
    
    /**
     * Allocate a new lottery thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer tickets from waiting threads
     *					to the owning thread.
     * @return	a new lottery thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
    	return new LotteryQueue(transferPriority);
    }
    
    public int getPriorityMaximum(){
    	return Integer.MAX_VALUE;
    }
    
    public int getPriorityMinimum(){
    	return 1;
    }
    
    protected class LotteryQueue extends PriorityQueue{
	    Random generator = new Random();
		protected LinkedList<ThreadState> waitQueue = new LinkedList<ThreadState>();
    	
    	LotteryQueue (boolean transferPriority){
    		super(transferPriority);
    	}
    	
    	/*
    	 * Holds the lottery and returns the next thread
    	 */
    	
		public KThread nextThread() {
            Lib.assertTrue(Machine.interrupt().disabled());

            System.out.println("LOTTERY-SCHEDULER :: In Next Thread");
            System.out.println("LOTTERY-SCHEDULER :: Total number of tickets = " + getTotalTickets());
			ThreadState currThreadState = null;
			int totalTickets = getTotalTickets();
			int winner;
			int cntr = 0;
			
			if(waitQueue.isEmpty())
				return null;			

			if(totalTickets > 0)
			 winner = generator.nextInt(getTotalTickets());
			else return null;

			
			for(Iterator itr = waitQueue.iterator(); itr.hasNext(); ){
				currThreadState = (ThreadState)itr.next();
				
				if(winner >= cntr && winner < cntr + currThreadState.getEffectivePriority()){
					currThreadState.acquire(this);					
					waitQueue.remove(currThreadState);

					return currThreadState.thread;
				}
					
				cntr += currThreadState.getEffectivePriority();
			}
			
			return null;
		}

		public void waitForAccess(KThread thread) {
			System.out.println("LOTTERY-SCHEDULER :: In Wait for Access");
			Lib.assertTrue(Machine.interrupt().disabled());
		    ThreadState waitingThreadState = getThreadState(thread);

		    Lib.assertTrue(getTotalTickets() + waitingThreadState.getPriority() < getPriorityMaximum());
		    
		    waitingThreadState.waitForAccess(this);		    
		    
		    waitQueue.add(getThreadState(thread));
		    if(owner != null){
		    	getThreadState(owner).donatePriority(waitingThreadState.getPriority());
		    }
		}
    	
		public int getTotalTickets(){
			int totalTickets = 0;
			int effectivePriority;
			
			System.out.println("LOTTERY-SCHEDULER :: Size of waitQueue: " + waitQueue.size());			
			
			for(ThreadState currState: waitQueue){
				effectivePriority = currState.getEffectivePriority();
				System.out.println("LOTTERY-SCHED :: Effective priority = " + effectivePriority);
				
				totalTickets += effectivePriority;
			}
System.out.println("LOTTERY-SCHEDULER :: RETURNING totalTickets");
			return totalTickets;
		}
		
    }//End lottery queue
    
    public static void selfTest(){
    	final Alarm a = new Alarm();

    	System.out.println("===========");
        System.out.println("Testing Lottery Scheduler");
        System.out.println("===========");
        final Lock l = new Lock();
        final Condition2 testCond = new Condition2(l);

        KThread t1 = new KThread(new Runnable(){
                public void run(){
                        System.out.println("Thread 1 :: sleeping");
                        l.acquire();
                        
                        testCond.sleep();
                        l.release();
                        System.out.println("Thread 1 :: awake.");
                }
        });

        KThread t2 = new KThread(new Runnable(){
                public void run(){
                        System.out.println("Thread 2 waking thread 1 in a second or so...");
                        a.waitUntil(1000000);
                        l.acquire();
                        testCond.wake();
                        l.release();
                        System.out.println("Thread 2 woke thread 1.");
                }
        });

        t1.fork();
        t2.fork();

        t1.join();
        t2.join();
    }
}
